/*
02-线性结构1 两个有序链表序列的合并
分数 15
作者 DS课程组
单位 浙江大学

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：

List Merge( List L1, List L2 );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; // 存储结点数据
    PtrToNode   Next; // 指向下一个结点的指针
};
typedef PtrToNode List; // 定义单链表类型

L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
*/

List Merge( List L1, List L2 ) {
    // 仅为头节点分配内容，其他节点直接使用L1,L2中的
    PtrToNode head = (PtrToNode)malloc(sizeof(struct Node));
    PtrToNode pn = head;
    
    PtrToNode p1 = L1->Next;
    PtrToNode p2 = L2->Next;
    while (p1!=NULL && p2!=NULL) {
        if (p1->Data <= p2->Data) {
            pn->Next = p1;
            p1 = p1->Next;
        } else {
            pn->Next = p2;
            p2 = p2->Next;
        }
        pn = pn->Next;
    }
    // L1或L2为NULL，接上另一个链表
    pn->Next = p1 !=NULL ? p1 : p2;
    // 输出时L1,L2为NULL
    L1->Next = NULL;
    L2->Next = NULL;
    
    return head;
}
